Class QuickSort<T extends java.lang.Comparable<? super T>>

java.lang.Object

TestTimes

QuickSort<T>

All Implemented Interfaces:

SortInterface<T>, TestTimesInterface

public class QuickSort<T extends java.lang.Comparable<? super T>>
extends TestTimes
implements SortInterface<T>

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	QuickSort.PivotType This enum specifies the pivot type that QuickSort will use.

Nested classes/interfaces inherited from interface TestTimesInterface

TestTimesInterface.MemoryUnits, TestTimesInterface.TimeUnits

Field Summary

Fields

Modifier and Type	Field and Description
private QuickSort.PivotType	pivotType

Constructor Summary

Constructors

Constructor and Description
QuickSort()

Method Summary

Modifier and Type	Method and Description
void	choosePivot(T[] array, int first, int last) This method selects the pivot according to the type of pivot specified.
QuickSort.PivotType	getPivotType() A getter for the PivotType being used.
private int	partition(T[] array, int first, int last) This method first finds the pivot p by calling choosePivot and then partitions and rearranges the elements of the array in the following manner:
private void	quickSort(T[] array, int first, int last) This is the recursive method that implements the QuickSort algorithm.
void	setPivotType(QuickSort.PivotType pivotType) The setter for the PivotType being used.
void	sort(T[] arrayToSort) This is the method that users will call to sort the specified array of Objects of type T using QuickSort.

Methods inherited from class TestTimes

addTestTime, getAverageMemoryUsage, getAverageTestTime, getLastMemoryUsage, getLastTestTime, getMemoryUnits, getMemoryUsages, getTestTimes, getTimeUnits, resetTestTimes, setMemoryUnits, setTimeUnits

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

pivotType

private QuickSort.PivotType pivotType

Constructor Detail

QuickSort

public QuickSort()

Method Detail

getPivotType

public QuickSort.PivotType getPivotType()

A getter for the PivotType being used. The default is FirstElement See QuickSort.PivotType

Returns:

The current PivotType being used.

setPivotType

public void setPivotType(QuickSort.PivotType pivotType)

The setter for the PivotType being used. See QuickSort.PivotType

Parameters:

pivotType - The PivotType to use.

sort

public void sort(T[] arrayToSort)

This is the method that users will call to sort the specified array of Objects of type T using QuickSort. The method of choosing the pivot is specified by properly setting the pivotType instance variable.

This method will call the quickSort method to perform the recursive sort.

The Comparable interface must either be implemented by T or a superclass of T.

When this method is done, the specified array is sorted.

Specified by:

sort in interface SortInterface<T extends java.lang.Comparable<? super T>>

Parameters:

arrayToSort - The array of Objects of type T to be sorted.

quickSort

private void quickSort(T[] array,
                       int first,
                       int last)

This is the recursive method that implements the QuickSort algorithm.

Parameters:

array - The array of Objects of type T to be sorted.

first - Index of the first entry of the array

last - Index of the last entry of the array

choosePivot

public void choosePivot(T[] array,
                        int first,
                        int last)

This method selects the pivot according to the type of pivot specified.

The chosen pivot will end up as the first element in the specified array.

Parameters:

array - The array of Objects of type T to be sorted.

first - Index of the first entry of the array

last - Index of the last entry of the array

partition

private int partition(T[] array,
                      int first,
                      int last)

This method first finds the pivot p by calling choosePivot and then partitions and rearranges the elements of the array in the following manner:

 
                { [ elements < p ] p [ elements ≥ p] }.
 

Parameters:

array - The array of Objects of type T to be sorted.

first - Index of the first entry of the array

last - Index of the last entry of the array

Returns:

The index of the location of the pivot p after the partition.